package 程序员面试金典;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class 最短超串 {
    public int[] shortestSeq(int[] big, int[] small) {
        int left=0,right=0;
        //起始位置
        int start=0;
        //统计匹配的字符串个数
        int match=0;
        //窗口大小
        int min=Integer.MAX_VALUE;
        Map<Integer, Integer> window = new HashMap<>();
        Map<Integer, Integer> needs = new HashMap<>();
        for (int i = 0; i < small.length; i++) {
            needs.put(small[i],1);
        }
        while (right<big.length){
            int num = big[right];
            if (needs.containsKey(num)){
                window.put(num,window.getOrDefault(num,0)+1);
                if (window.get(num)==1)
                    match++;
            }
            right++;
            while (match==small.length){
                //更新最小窗口
                if (right-left<min){
                    start=left;
                    min=right-left;
                }
                int i = big[left];
                if (needs.containsKey(i)){
                    window.put(i,window.getOrDefault(i,0)-1);
                    if (window.get(i)<1)
                        match--;
                }
                left++;
            }
        }
        return min==Integer.MAX_VALUE?new int[]{} : new int[]{start,start+min-1};
    }
}
